﻿using System;

class MergeSort
{
    static void Main()
    {
        int[] array = { 5, 9, 4, 1, 10, 3, 17, 2, 1, 5, 1 };

        MyMergeSort(array, 0, array.Length - 1);

        string sorted = string.Join(", ", array);
        Console.WriteLine(sorted);
    }

    private static void MyMergeSort(int[] array, int left, int right)
    {
        if (left < right)
        {
            int mid = (left + right) / 2;

            MyMergeSort(array, left, mid);
            MyMergeSort(array, mid + 1, right);

            int leftSize = mid - left + 1;
            int[] leftPart = new int[leftSize];
            int rightSize = right - mid;
            int[] rightPart = new int[rightSize];

            Array.Copy(array, left, leftPart, 0, leftSize);
            Array.Copy(array, mid + 1, rightPart, 0, rightSize);

            int leftIndexPtr = 0;
            int rightIndexPtr = 0;
            while (left <= right)
            {
                if (leftIndexPtr == leftSize)
                {
                    array[left] = rightPart[rightIndexPtr];
                    rightIndexPtr++;
                }
                else if (rightIndexPtr == rightSize)
                {
                    array[left] = leftPart[leftIndexPtr];
                    leftIndexPtr++;
                }
                else if (leftPart[leftIndexPtr] < rightPart[rightIndexPtr])
                {
                    array[left] = leftPart[leftIndexPtr];
                    leftIndexPtr++;
                }
                else
                {
                    array[left] = rightPart[rightIndexPtr];
                    rightIndexPtr++;
                }

                left++;
            }
        }
    }
}
